package 每日一题;

import publicClass.TreeNode;

/**
 * 1038. 从二叉搜索树到更大和树
 * 给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
 *
 * 提醒一下， 二叉搜索树 满足下列约束条件：
 *
 * 节点的左子树仅包含键 小于 节点键的节点。
 * 节点的右子树仅包含键 大于 节点键的节点。
 * 左右子树也必须是二叉搜索树。
 * 提示：
 *
 * 树中的节点数在 [1, 100] 范围内。
 * 0 <= Node.val <= 100
 * 树中的所有值均 不重复 。
 * https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree
 */
public class T1038_从二叉搜索树到更大和树 {

    int temp = 0;

    //当前节点的新值 等于 左子树最大值+当前节点的值 ,
    public TreeNode bstToGst(TreeNode root) {

        dfs(root);
        return root;

    }


    // 右 中 左的方式遍历 加上一个数
    public void dfs(TreeNode root) {


        if (root.right != null) {
            dfs(root.right);
        }

        temp += root.val;
        root.val = temp;

        if (root.left != null) {
            dfs(root.left);
        }

    }



}
